On the state of strength‐three covering arrays

A covering array of size N, strength t, degree k, and order υ is a k × N array on υ symbols in which every t × N subarray contains every possible t × 1 column at least once. We present explicit constructions, constructive upper bounds on the size of various covering arrays, and compare our results with those of a commercial product. Applications of covering arrays include software testing, drug screening, and data compression. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 217–238, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10002     

Three-divisible families of skew lines on a smooth projective quintic

We give an example of a family of 15 skew lines on a quintic such that its class is divisible by 3. We study properties of the codes given by arrangements of disjoint lines on quintics.

     

Alternating-Sign Matrices and Domino Tilings (Part II)

We continue the study of the family of planar regions dubbed Aztec diamonds in our earlier article and study the ways in which these regions can be tiled by dominoes. Two more proofs of the main formula are given. The first uses the representation theory of GL(n). The second is more combinatorial and produces a generating function that gives not only the number of domino tilings of the Aztec diamond of order n but also information about the orientation of the dominoes (vertical versus horizontal) and the accessibility of one tiling from another by means of local modifications. Lastly, we explore a connection between the combinatorial objects studied in this paper and the square-ice model studied by Lieb.     

An edge-reduction algorithm for the vertex cover problem

An approximation algorithm for the vertex cover problem is proposed with performance ratio on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S₁ such that where S^∗ is an optimal cover and ξ is an error bound identified.     

Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems

We consider an -hard variant (Δ-Max-ATSP) and an -hard relaxation (Max-3-DCC) of the classical traveling salesman problem. We present a -approximation algorithm for Δ-Max-ATSP and a -approximation algorithm for Max-3-DCC with polynomial running time. The results are obtained via a new way of applying techniques for computing undirected cycle covers to directed problems.     

Compact Manifolds Covered by a Torus

Let X be a compact complex manifold which is the image of a complex torus by a holomorphic surjective map A→X. We prove that X is Kähler and that up to a finite étale cover, X is a product of projective spaces by a torus.     

Orthogonal Double Covers of Complete Graphs by Caterpillars of Diameter 5

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection = {G_i|i = 1,2, . . . ,n} of spanning subgraphs of K_n, all isomorphic to G, with the property that every edge of K_n belongs to exactly two members of and any two distinct members of share exactly one edge. A caterpillar of diameter five is a tree arising from a path with six vertices by attaching pendant vertices to some or each of its vertices of degree two. We show that for any caterpillar of diameter five there exists an ODC of the complete graph K_n.     

On finding a large number of 3D points with a small diameter

Given a set S of n points in R³, we wish to decide whether S has a subset of size at least k with Euclidean diameter at most r. It is unknown whether this decision problem is NP-hard. The two closely related optimization problems, (i) finding a largest subset of diameter at most r, and (ii) finding a subset of the smallest diameter of size at least k, were recently considered by Afshani and Chan. For maximizing the size, they presented several polynomial-time algorithms with constant approximation factors, the best of which has a factor of . For maximizing the diameter, they presented a polynomial-time approximation scheme. In this paper, we present improved approximation algorithms for both optimization problems. For maximizing the size, we present two algorithms: the first one improves the approximation factor to 2.5 and the running time by an O(n) factor; the second one improves the approximation factor to 2 and the running time by an O(n²) factor. For minimizing the diameter, we improve the running time of the PTAS from O(nlogn+2^O(1/ε3)n) to O(nlogn+2^{O(1/(ε1.5logε))}n).